#include<iostream>
using namespace std;

template<class T>
class maxHeap{
//起始编号为0，若一个非叶节点的位置为i，那么它的左孩子和右孩子位置为2*i+1和2*i+2
private:
    T*heap;
    int capacity;//最大容量
    int size;//当前大小
public:
    maxHeap(T*&array,int c,int length);
    ~maxHeap(){
        delete[]this->heap;
    };

    bool isEmpty()const{
        return size==0;
    }
    int getSize()const{
        return this->size;
    }
    T&top();
    void pop();
    void push(T&e);
};

template<class T>
maxHeap<T>::maxHeap(T*&array,int c,int length){
    /*
    也可通过初始化函数初始化堆
    在本代码中，堆不可扩充，于是在构造函数中为堆直接开辟容量大小的空间
    如果按照《数据结构、算法与应用，C++描述(第二版)》表示，无需开辟空间，
    直接将heap指向已经存在的一个数组即可
    */
    //初始化大根堆
    if(length>c||length==0){
        cout<<"The value of length is invalid."<<endl;
        throw 0;
    }
    this->capacity=c;
    heap=new T[c];
    this->size=length;
    for(int i=0;i<length;i++)
        heap[i]=array[i];
    //调整数组至大根堆
    //从最后一个非叶节点开始
    for(int i=(length-2)/2;i>=0;i--){
        //heap[i]为当前需要调整的节点
        int child=i*2+1;//当前节点的左孩子(如果存在)
        while(child<length){
            if(child+1<length&&heap[child]<heap[child+1])
                child++;

            if(heap[child]>heap[i]){
                T cur=heap[child];
                heap[child]=heap[i];
                heap[i]=cur;
                i=child;
            }
            else
                break;
            child=i*2+1;
        }
    }
}

template<class T>
T& maxHeap<T>::top(){
    //获取根节点的值
    if(!this->isEmpty())
        return heap[0];
    else
        throw 0;
}

template<class T>
void maxHeap<T>::pop(){
    //删除根节点(也只能删除根节点)
    //删除根节点后，将最后一个节点调至根节点，再层层向下调整
    if(this->isEmpty())
    {
        cout<<"The maxHeap is empty."<<endl;
        return;
    }
    this->heap[0]=this->heap[--size];
    int i=0,child=1;//此节点和它的较大孩子
    while(child<this->size){
        //先寻找孩子中较大的那个
        if(child+1<this->size&&heap[child]<heap[child+1])
            child++;
        
        //此时判断节点是否稳定，否则向下调整位置
        if(heap[i]<heap[child]){
            T cur=heap[child];
            heap[child]=heap[i];
            heap[i]=cur;
            i=child;
        }
        else
            break;
        child=i*2+1;
    }
}

template<class T>
void maxHeap<T>::push(T&e){
    /*
    如果堆可以扩充，只需要将堆的长度乘2即可
    后续操作没有变化(因为堆的有效值位置未发生变化)
    */
    //将新节点添加进堆中
    if(size==capacity){
        cout<<"The maxHeap is full."<<endl;
        return;
    }
    int i=size,father=(i-1)/2;
    heap[size++]=e;
     
    //此时判断节点是否稳定，否则向上调整位置
    while(i!=0&&heap[i]>heap[father]){
        T cur=heap[father];
        heap[father]=heap[i];
        heap[i]=cur;
        i=father;
        father=(i-1)/2;
    }
}

int main(){
    int*array=new int[6];
    array[0]=2;
    array[1]=5;
    array[2]=1;
    array[3]=9;
    array[4]=4;
    array[5]=3;
    maxHeap<int>h(array,10,6);

    for(int i=0;i<6;i++){
        cout<<"Current top is: "<<h.top()<<" Current size is: "<<h.getSize()<<endl;
        h.pop();
    }
    
    int*a=new int;

    *a=11;
    h.push(*a);

    *a=9;
    h.push(*a);

    *a=17;
    h.push(*a);
    cout<<h.top()<<endl;

    delete []array;
	delete a;
    return 0;
}